Scheduling Concepts

Scheduling Concepts

In order to understand the differences between scheduling methods you need to know some basic concepts.

Tick Interrupts

In normal operation, the kernel pauses to make scheduling decisions every 10 milliseconds in every CPU. The duration of this interval, which is called the "tick" because it is the metronomic beat of the scheduler, is defined in sys/param.h. Every CPU is normally interrupted by a timer every tick interval. (However, the CPUs in a multiprocessor are not necessarily synchronized. Different CPUs may take tick interrupts at a different times.)

During the tick interrupt the kernel updates accounting values, does other housekeeping work, and chooses which process to run next--usually the interrupted process, unless a process of superior priority has become ready to run. The tick interrupt is the mechanism that makes IRIX scheduling "preemptive"; that is, it is the mechanism that allows a high-priority process to take a CPU away from a lower-priority process.

Before the kernel returns to the chosen process, it checks for pending signals, and may divert the process into a signal handler.

You can stop the tick interrupt in selected CPUs in order to keep these interruptions from interfering with real-time programs--see "Making a CPU Nonpreemptive".

Time Slices

Each process has a guaranteed time slice, which is the amount of time it is normally allowed to execute without being preempted. By default the time slice is 3 ticks, or 30 ms. A typical process is usually blocked for I/O before it reaches the end of its time slice.

At the end of a time slice, the kernel chooses which process to run next on the same CPU based on process priorities. When runnable processes have the same priority, the kernel runs them in turn.

Priorities

Every process that is ready to run (not blocked on I/O or a semaphore) is listed in a queue of processes. (There are actually multiple queues, as described in a later topic.) Every process has a priority and a "nice" value. When a CPU needs a process to run, it normally takes the one with the lowest sum of priority and nice value. Thus a lower-numbered priority value gives a process a superior priority to run.

The specific priority values are shown in Table 6-1. The constant identifiers are defined in sys/schedctl.h.

Priority Ranges
Numeric Range Purpose Identifiers
30 ... 39 Real-time and other high-priority processes NDPHIMAX ... NDPHIMIN
40 ... 127 Normal user processes with degrading priorities NDPNORMAX ... NDPNORMIN
40 ... 127 Processes with assigned, nondegrading priorities NDPNORMAX ... NDPNORMIN
128 ... 254 Batch jobs and other low-priority processes NDPLOMAX ... NDPLOMIN

Priority Ranges
Numeric Range	Purpose	Identifiers
30 ... 39	Real-time and other high-priority processes	NDPHIMAX ... NDPHIMIN
40 ... 127	Normal user processes with degrading priorities	NDPNORMAX ... NDPNORMIN
40 ... 127	Processes with assigned, nondegrading priorities	NDPNORMAX ... NDPNORMIN
128 ... 254	Batch jobs and other low-priority processes	NDPLOMAX ... NDPLOMIN

Note that the names ending in MAX correspond to the lowest numbers. This reflects the fact that processes with lower numerical priority values have superior priority for use of the system; while those with higher numbers have inferior priority.

Aging Priorities

In order to favor I/O bound processes and to penalize CPU-bound processes, IRIX "ages" or "degrades" the priority of any normal process as it runs. The longer a process runs without blocking, the worse its priority becomes. When the process finally suspends voluntarily (to wait for I/O or some event), its priority is restored.

Scheduler Queues

The kernel maintains not one but several different scheduling queues, each containing processes that are scheduled under a different set of rules. These rules are covered in the following topics. The queues are listed in Table 6-2.

Scheduler Queues
Queue Processes and Discipline
Kernel Kernel code
Real-time Processes with fixed priorities between 30 and 39
Time-sharing Processes with priorities between 40 and 127 (priorities in this range can be either degrading or nondegrading)
Batch Batch processes with priorities between 128 and 254
Deadline Processes under the deadline scheduling rules
Gang Processes under the gang scheduling rules with priorities less than 128
Gang-batch Processes under the gang scheduling rules with priorities of 128 or greater

Scheduler Queues
Queue	Processes and Discipline
Kernel	Kernel code
Real-time	Processes with fixed priorities between 30 and 39
Time-sharing	Processes with priorities between 40 and 127 (priorities in this range can be either degrading or nondegrading)
Batch	Batch processes with priorities between 128 and 254
Deadline	Processes under the deadline scheduling rules
Gang	Processes under the gang scheduling rules with priorities less than 128
Gang-batch	Processes under the gang scheduling rules with priorities of 128 or greater

You can list the names of the queues and their associated priority-range numbers using

pset -q